/*
 * @lc app=leetcode.cn id=436 lang=typescript
 *
 * [436] 寻找右区间
 */

// @lc code=start
function findRightInterval(intervals: number[][]): number[] {
  const n = intervals.length;
  const startIdx: number[][] = new Array(n).fill(0).map((_) => new Array(2).fill(0));
  // 将每个区间的起始点和下标存入数组
  for (let i = 0; i < n; i++) {
    startIdx[i][0] = intervals[i][0];
    startIdx[i][1] = i;
  }
  // 排序
  startIdx.sort((a: number[], b: number[]) => a[0] - b[0]);

  // 二分查找，找到第一个大于等于当前右区间的下标
  const ans = new Array(n).fill(-1);
  for (let i = 0; i < n; i++) {
    let l = 0;
    let r = n - 1;
    let mid: number;
    let res = -1;
    while (l <= r) {
      mid = l + ((r - l) >> 1);
      if (startIdx[mid][0] >= intervals[i][1]) {
        res = startIdx[mid][1];
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    ans[i] = res;
  }
  return ans;
}
// @lc code=end
